{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 经典排序算法\n",
    "再次深入学习并使用 Java 实现\n",
    "本部分涵盖了十种经典的排序算法，这些算法对于理解和掌握数据结构与算法的基础至关重要。\n",
    "\n",
    "> 资料来源于 [十大经典排序算法 Java实现](https://blog.csdn.net/qq_43794633/article/details/121612149)\n",
    "\n",
    "**常见的经典算法的特点如下：**\n",
    "\n",
    "| 排序算法                  | 时间复杂度（最好） | 时间复杂度（平均） | 时间复杂度（最坏） | 排序方式  | 空间复杂度 | 稳定性 | 特点                                                                             |\n",
    "|------------------------|------------------|------------------|------------------|-----------|------------|------|--------------------------------------------------------------------------------|\n",
    "| 冒泡排序 (Bubble Sort)    | O(n)             | O(n²)            | O(n²)            | In-place  | O(1)       | 稳定   | 比较相邻元素并交换位置，重复进行直到无需再交换。简单易懂，适合教学。                 |\n",
    "| 选择排序 (Selection Sort) | O(n²)            | O(n²)            | O(n²)            | In-place  | O(1)       | 不稳定 | 每次从未排序的部分选出最小（或最大）的元素放到已排序序列的末尾。效率较低。           |\n",
    "| 插入排序 (Insertion Sort) | O(n)             | O(n²)            | O(n²)            | In-place  | O(1)       | 稳定   | 将每个元素插入到已排序序列中的适当位置，适合小规模或基本有序的数据集。             |\n",
    "| 希尔排序 (Shell Sort)     | 取决于间隔序列   | 取决于间隔序列   | 取决于间隔序列   | In-place  | O(1)       | 不稳定 | 通过比较相隔一定间隔的元素进行插入排序，间隔逐渐减小至1，性能优于O(n²)。            |\n",
    "| 归并排序 (Merge Sort)     | N/A              | O(n $\\log_{2}{n}$)       | O(n $\\log_{2}{n}$)       | Out-place | O(n)       | 稳定   | 分治法，递归地将数组分成两半，分别排序后再合并。适用于大数据量排序。                 |\n",
    "| 快速排序 (Quick Sort)     | O(n $\\log_{2}{n}$)       | O(n $\\log_{2}{n}$)       | O(n²)            | In-place  | O($\\log_{2}{n}$)   | 不稳定 | 分治法，选择一个基准值，将小于基准的元素移到左边，大于基准的移到右边。               |\n",
    "| 堆排序 (Heap Sort)        | N/A              | O(n $\\log_{2}{n}$)       | O(n $\\log_{2}{n}$)       | In-place  | O(1)       | 不稳定 | 利用堆数据结构进行排序，构建最大堆或最小堆后移除堆顶元素。原地排序。                |\n",
    "| 计数排序 (Counting Sort)  | O(n + k)         | O(n + k)         | O(n + k)         | Out-place | O(k)       | 稳定   | 适用于整数排序，统计每个数值出现次数，根据计数结果输出排序结果。线性时间复杂度。     |\n",
    "| 桶排序 (Bucket Sort)      | O(n + k)         | O(n + k)         | O(n²)            | Out-place | O(n)       | 稳定   | 将区间分为多个桶(k个桶)，每个桶内使用其他排序算法，最后合并桶的结果。适用于均匀分布的数据。 |\n",
    "| 基数排序 (Radix Sort)     | O(d·(n + k))     | O(d·(n + k))     | O(d·(n + k))     | Out-place | O(n + k)   | 稳定   | 对整数的每一位从低位到高位依次进行排序，通常使用计数排序作为子程序。适合整数排序。  |\n",
    "\n",
    "其中，“稳定性”指的是相同键值的记录在排序前后的相对顺序是否保持不变；“空间复杂度”描述了除了输入数据之外的额外内存需求；而时间复杂度则描述了算法执行所需的时间与输入数据大小的关系。注意，希尔排序和桶排序的时间复杂度取决于具体实现细节。\n",
    "\n",
    "排序算法可以分为内部排序算法和外部排序算法：在内存中进行的称为内部排序算法(In-place)，也就是这里所说的这十种算法；相应的，当数据量很大时无法全部拷贝到内存需要使用外存，称为外部排序算法(Out-place)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1、冒泡排序（Bubble Sort）\n",
    "**算法步驟**\n",
    "\n",
    "1. 比较相邻的元素，如果第一个比第二个大，就交换它们两个；\n",
    "1. 对每一对相邻元素作同样的比价，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；\n",
    "1. 针对所有的元素重复以上的步骤，除了数组最后已经排好序的数组；  \n",
    "重复步骤1~3，直到排序完成。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原始数组：\n",
      "1 4 5 2 7 11 6 \n",
      "排序后的数组：\n",
      "1 2 4 5 6 7 11 "
     ]
    }
   ],
   "source": [
    "public class BubbleSort {\n",
    "\n",
    "    /**\n",
    "     * 冒泡排序算法实现。\n",
    "     * \n",
    "     * @param arr 待排序的整型数组\n",
    "     */\n",
    "    public static void bubbleSort(int[] arr) {\n",
    "        int len = arr.length; // 获取数组长度\n",
    "        \n",
    "        // 外层循环控制排序趟数，共需进行 len - 1 趟排序\n",
    "        for (int i = 0; i < len - 1; i++) {\n",
    "            boolean flag = true; // 标记变量，用于检测当前趟是否发生了交换\n",
    "            \n",
    "            // 内层循环负责每趟的具体比较和交换操作\n",
    "            // 每一趟将未排序部分的最大元素冒泡到最后\n",
    "            for (int j = 0; j < len - i - 1; j++) {\n",
    "                // 当前元素大于下一个元素时，进行交换\n",
    "                if (arr[j] > arr[j + 1]) {\n",
    "                    int tmp = arr[j]; // 临时变量用于保存当前元素\n",
    "                    arr[j] = arr[j + 1]; // 将较小的元素移动到前面\n",
    "                    arr[j + 1] = tmp; // 将较大的元素移动到后面\n",
    "                    flag = false; // 发生了交换，标记变量置为 false\n",
    "                }\n",
    "            }\n",
    "            \n",
    "            // 如果某趟排序没有发生任何交换，则说明数组已经有序，可以直接结束排序\n",
    "            if (flag) {\n",
    "                break;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "// 辅助方法，用于打印数组中的元素\n",
    "private static void printArray(int[] arr) {\n",
    "    for (int num : arr) \n",
    "        System.out.print(num + \" \");\n",
    "}\n",
    "\n",
    "// 初始化数组\n",
    "int [] array = {1,4,5,2,7,11,6};\n",
    "System.out.println(\"原始数组：\");\n",
    "printArray(array);\n",
    "// 排序\n",
    "BubbleSort.bubbleSort(array);\n",
    "System.out.println(\"\\n排序后的数组：\");\n",
    "// 打印排序后的数组\n",
    "printArray(array);\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **外层循环** (`for (int i = 0; i < len - 1; i++)`): 控制排序的趟数。由于每趟都会把一个元素放置到正确的位置，所以只需要进行`len - 1`趟排序即可。\n",
    "\n",
    "2. **内部循环** (`for (int j = 0; j < len - i - 1; j++)`): 在每趟排序中，将未排序部分的最大元素移动到正确的位置。随着排序的进行，已排序的部分逐渐增加，未排序部分逐渐减少。\n",
    "\n",
    "3. **交换元素** (`if (arr[j] > arr[j + 1])`): 如果当前元素大于其后面的元素，则交换这两个元素的位置。这样，较大的元素会逐渐向数组的末尾移动，就像气泡上升一样，因此得名“冒泡排序”。\n",
    "\n",
    "4. **提前退出** (`if (flag) { break; }`): 如果在某趟排序过程中没有发生任何交换，说明数组已经是有序的，此时可以提前结束排序过程，提高效率。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2、选择排序（Selection Sort）\n",
    "**算法步驟**\n",
    "\n",
    "1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；\n",
    "1. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；\n",
    "1. 重复第2步，直到所有元素均排序完毕。\n",
    "\n",
    "选择排序通过不断地选择未排序部分的最小值并将其放置在已排序部分的末尾，最终完成整个数组的排序。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原始数组:\n",
      "64 34 25 12 22 11 90 \n",
      "排序后的数组:\n",
      "11 12 22 25 34 64 90 "
     ]
    }
   ],
   "source": [
    "public class SelectionSort {\n",
    "\n",
    "    /**\n",
    "     * 选择排序算法实现。\n",
    "     * \n",
    "     * @param arr 待排序的整型数组\n",
    "     */\n",
    "    public static void selectionSort(int[] arr) {\n",
    "        int len = arr.length; // 获取数组长度\n",
    "        \n",
    "        // 外层循环控制排序趟数，共需进行 len - 1 趟排序\n",
    "        for (int i = 0; i < len - 1; i++) {\n",
    "            int minValIndex = i; // 假设当前索引 i 的元素是最小值\n",
    "            \n",
    "            // 内层循环负责找到未排序部分的最小元素的索引\n",
    "            for (int j = i + 1; j < len; j++) {\n",
    "                // 如果找到更小的元素，则更新最小值的索引\n",
    "                if (arr[minValIndex] > arr[j]) {\n",
    "                    minValIndex = j;\n",
    "                }\n",
    "            }\n",
    "            \n",
    "            // 如果最小值的索引发生变化，则交换元素\n",
    "            if (minValIndex != i) {\n",
    "                int tmp = arr[i]; // 临时变量用于保存当前索引 i 的值\n",
    "                arr[i] = arr[minValIndex]; // 将找到的最小值放到正确的位置\n",
    "                arr[minValIndex] = tmp; // 将原来的值放到最小值的位置\n",
    "            }\n",
    "        }\n",
    "    }   \n",
    "}\n",
    "\n",
    "// 测试排序算法\n",
    "int[] arr = {64, 34, 25, 12, 22, 11, 90};\n",
    "System.out.println(\"原始数组:\");\n",
    "printArray(arr); // 打印原始数组\n",
    "SelectionSort.selectionSort(arr); // 对数组进行选择排序\n",
    "System.out.println(\"\\n排序后的数组:\");\n",
    "printArray(arr); // 打印排序后的数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **初始化最小值索引** (`int minValIndex = i;`): 假设当前索引 `i` 的元素是最小值。\n",
    "\n",
    "2. **内层循环** (`for (int j = i + 1; j < len; j++)`): 在每趟排序中，从 `i+1` 开始遍历到数组的末尾，寻找未排序部分的最小值的索引。\n",
    "\n",
    "3. **更新最小值索引** (`if (arr[minValIndex] > arr[j])`): 如果找到了比当前假设的最小值还要小的元素，就更新最小值的索引 `minValIndex`。\n",
    "\n",
    "4. **交换元素** (`if (minValIndex != i) { ... }`): 如果在当前趟排序中找到了更小的元素，则将该元素与当前位置 `i` 的元素交换，从而将最小值移动到正确的位置。\n",
    "\n",
    "5. **外层循环** (`for (int i = 0; i < len - 1; i++)`): 控制排序的趟数。每趟排序都将未排序部分的最小值移动到已排序部分的末尾。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 3、插入排序（Insertion Sort）\n",
    "**算法步驟**\n",
    "\n",
    "1. 首先从第一个元素开始，该元素被认为是有序的；\n",
    "1. 取出下一个元素，在已经排序的元素序列中从后往前进行扫描；\n",
    "1. 如果该已排好序的元素大于新元素，则将该元素移到下一位置；\n",
    "1. 重复步骤3一直往前进行扫描比较，直到找到已排序的元素小于或者等于新元素的位置；\n",
    "1. 将新元素插入到该位置后；\n",
    "1. 重复步骤2~5。\n",
    "\n",
    "插入排序通过不断地将未排序部分的第一个元素插入到已排序部分的合适位置，最终完成整个数组的排序。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原始数组:\n",
      "64 34 25 12 22 11 90 \n",
      "排序后的数组:\n",
      "11 12 22 25 34 64 90 "
     ]
    }
   ],
   "source": [
    "public class InsertionSort {\n",
    "\n",
    "    /**\n",
    "     * 插入排序算法实现。\n",
    "     * \n",
    "     * @param arr 待排序的整型数组\n",
    "     */\n",
    "    public static void insertionSort(int[] arr) {\n",
    "        // 从第二个元素开始遍历数组\n",
    "        for (int i = 1; i < arr.length; i++) {\n",
    "            int val = arr[i]; // 当前需要插入的元素值\n",
    "            int j = i; // 初始化索引 j 为当前元素的索引\n",
    "            \n",
    "            // 将当前元素向后移动，直到找到合适的位置\n",
    "            while (j > 0 && val < arr[j - 1]) {\n",
    "                arr[j] = arr[j - 1]; // 将当前元素之前的元素向后移动一位\n",
    "                j--; // 向前检查下一个元素\n",
    "            }\n",
    "            \n",
    "            // 将当前元素插入到正确的位置\n",
    "            arr[j] = val;\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "// 测试排序算法\n",
    "int[] arr = {64, 34, 25, 12, 22, 11, 90};\n",
    "System.out.println(\"原始数组:\");\n",
    "printArray(arr); // 打印原始数组\n",
    "InsertionSort.insertionSort(arr); // 对数组进行插入排序\n",
    "System.out.println(\"\\n排序后的数组:\");\n",
    "printArray(arr); // 打印排序后的数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **初始化当前元素** (`int val = arr[i]; int j = i;`): 将当前索引 `i` 的元素值存储在变量 `val` 中，并将索引 `j` 初始化为 `i`。\n",
    "\n",
    "2. **内层循环** (`while (j > 0 && val < arr[j - 1])`): 该循环负责将当前元素向后移动，直到找到一个比它大的元素或者到达数组的起始位置。具体来说：\n",
    "   - `j > 0` 确保不会越界。\n",
    "   - `val < arr[j - 1]` 检查当前元素是否小于前一个元素，如果是，则继续移动。\n",
    "\n",
    "3. **移动元素** (`arr[j] = arr[j - 1]; j--;`): 将当前元素之前的元素向后移动一位，并将索引向前移动一位。\n",
    "\n",
    "4. **插入元素** (`arr[j] = val;`): 当循环结束时，`j` 指向了当前元素应该插入的位置，此时将 `val` 插入到该位置。\n",
    "\n",
    "5. **外层循环** (`for (int i = 1; i < arr.length; i++)`): 从数组的第二个元素开始遍历，因为第一个元素默认已经“排序”（即单个元素自然有序）。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4、希尔排序（Shell Sort）\n",
    "**算法步驟**\n",
    "\n",
    "1. 选择一个增量序列${t_1, t_2, …, t_k}$；\n",
    "1. 按增量序列个数k，对序列进行k趟排序；\n",
    "1. 每趟排序，根据对应的增量t，将待排序列分割成若干长度为m的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。\n",
    "1. 其中，增量$gap = \\frac{length}{2}$，缩小增量继续以$gap = \\frac{gap}{2}$的方式，这种增量选择我们可以用一个序列来表示，${\\frac{n}{2}, \\frac{n}{4}, …, 1}$，称为增量序列。一般的增量序列都选择以上说明的这个，但不一定是最优的。\n",
    "\n",
    "希尔排序通过逐步缩小增量来进行多轮插入排序，从而提高了排序的效率，尤其是对于大规模数据集时，其性能通常优于简单的插入排序。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原始数组:\n",
      "64 34 25 12 22 11 90 \n",
      "排序后的数组:\n",
      "11 12 22 25 34 64 90 "
     ]
    }
   ],
   "source": [
    "public class ShellSort {\n",
    "\n",
    "    /**\n",
    "     * 希尔排序算法实现。\n",
    "     * \n",
    "     * @param arr 待排序的整型数组\n",
    "     */\n",
    "    public static void shellSort(int[] arr) {\n",
    "        int len = arr.length; // 获取数组长度\n",
    "        int tmp, j; // 临时变量用于交换元素，j 用于索引\n",
    "        \n",
    "        // 逐步缩小增量 gap\n",
    "        for (int gap = len / 2; gap >= 1; gap /= 2) {\n",
    "            // 对数组进行增量 gap 的插入排序\n",
    "            for (int i = gap; i < len; i++) {\n",
    "                tmp = arr[i]; // 当前需要插入的元素值\n",
    "                j = i - gap; // 初始化索引 j 为当前元素减去增量\n",
    "                \n",
    "                // 将当前元素向后移动，直到找到合适的位置\n",
    "                while (j >= 0 && arr[j] > tmp) {\n",
    "                    arr[j + gap] = arr[j]; // 将当前元素之前的元素向后移动一位\n",
    "                    j -= gap; // 向前检查下一个元素\n",
    "                }\n",
    "                \n",
    "                // 将当前元素插入到正确的位置\n",
    "                arr[j + gap] = tmp;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "\n",
    "// 测试排序算法\n",
    "int[] arr = {64, 34, 25, 12, 22, 11, 90};\n",
    "System.out.println(\"原始数组:\");\n",
    "printArray(arr); // 打印原始数组\n",
    "ShellSort.shellSort(arr); // 对数组进行希尔排序\n",
    "System.out.println(\"\\n排序后的数组:\");\n",
    "printArray(arr); // 打印排序后的数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **初始化增量** (`int gap = len / 2;`): 希尔排序的核心思想是先将数组分割成几个子数组，分别对这些子数组进行插入排序。初始时，增量 `gap` 设置为数组长度的一半。\n",
    "\n",
    "2. **逐步缩小增量** (`for (int gap = len / 2; gap >= 1; gap /= 2)`): 逐步减小增量 `gap`，直到 `gap` 为 1。每一轮增量 `gap` 的插入排序都是独立的，当 `gap` 减小到 1 时，相当于一次普通的插入排序。\n",
    "\n",
    "3. **插入排序** (`for (int i = gap; i < len; i++)`): 对当前增量 `gap` 下的数组进行插入排序。从索引 `gap` 开始遍历数组，因为索引 `0` 到 `gap - 1` 之间的元素已经在前一轮排序中处理过了。\n",
    "\n",
    "4. **移动元素** (`while (j >= 0 && arr[j] > tmp)`): 将当前元素向后移动，直到找到一个比它大的元素或者到达数组的起始位置。具体来说：\n",
    "   - `j >= 0` 确保不会越界。\n",
    "   - `arr[j] > tmp` 检查当前元素是否小于前一个元素，如果是，则继续移动。\n",
    "\n",
    "5. **插入元素** (`arr[j + gap] = tmp;`): 当循环结束时，`j` 指向了当前元素应该插入的位置，此时将 `tmp` 插入到该位置。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5、归并排序（Merge Sort）\n",
    "**算法步驟**\n",
    "\n",
    "1. 如果待排序列只有一个元素，则直接返回，否则将长度为n的待排序列分成两个长度为$\\frac{n}{2}$的子序列，递归进行调用进行分割知道每个子序列中只有一个元素；\n",
    "1. 此时的每个子序列被认为是有序的，然后递归调用的返回子序列进行两两合并；\n",
    "1. 合并过程中完成排序操作，具体操作为设定两个指针，分别指向两个已经排序子序列的起始位置；\n",
    "1. 比较两个指针所指向的元素，选择相对小的元素放入到合并返回的数组，并移动指针到下一位置；\n",
    "1. 重复步骤3~4直到某一指针达到序列尾；\n",
    "1. 将另一序列剩下的所有元素直接复制到合并序列尾，最终得到的新序列就是有序序列。\n",
    "\n",
    "归并排序是一种高效的排序算法，它通过递归地将数组拆分成更小的部分，然后将这些部分重新组合成有序数组。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原始数组:\n",
      "64 34 25 12 22 11 90 \n",
      "排序后的数组:\n",
      "11 12 22 25 34 64 90 "
     ]
    }
   ],
   "source": [
    "import java.util.Arrays;\n",
    "\n",
    "public class MergeSort {\n",
    "\n",
    "    /**\n",
    "     * 归并排序算法实现。\n",
    "     * \n",
    "     * @param arr 待排序的整型数组\n",
    "     * @return 排序后的数组\n",
    "     */\n",
    "    public static int[] mergeSort(int[] arr) {\n",
    "        int len = arr.length; // 获取数组长度\n",
    "        \n",
    "        // 如果数组长度小于2，则直接返回数组，无需排序\n",
    "        if (len < 2) {\n",
    "            return arr;\n",
    "        }\n",
    "\n",
    "        // 计算中间索引\n",
    "        int midIdx = len / 2;\n",
    "        \n",
    "        // 递归地对左半部分进行归并排序\n",
    "        int[] leftSorted = mergeSort(Arrays.copyOfRange(arr, 0, midIdx));\n",
    "        \n",
    "        // 递归地对右半部分进行归并排序\n",
    "        int[] rightSorted = mergeSort(Arrays.copyOfRange(arr, midIdx, len));\n",
    "        \n",
    "        // 合并两个已排序的数组\n",
    "        return merge(leftSorted, rightSorted);\n",
    "    }\n",
    "\n",
    "    /**\n",
    "     * 合并两个已排序的数组。\n",
    "     * \n",
    "     * @param arrLeft 左侧已排序的数组\n",
    "     * @param arrRight 右侧已排序的数组\n",
    "     * @return 合并后的已排序数组\n",
    "     */\n",
    "    private static int[] merge(int[] arrLeft, int[] arrRight) {\n",
    "        int leftLen = arrLeft.length; // 左侧数组的长度\n",
    "        int rightLen = arrRight.length; // 右侧数组的长度\n",
    "        int leftIdx = 0; // 左侧数组的索引\n",
    "        int rightIdx = 0; // 右侧数组的索引\n",
    "        int idx = 0; // 结果数组的索引\n",
    "        \n",
    "        // 初始化结果数组\n",
    "        int[] result = new int[leftLen + rightLen];\n",
    "        \n",
    "        // 合并两个数组中的元素\n",
    "        while (leftIdx < leftLen && rightIdx < rightLen) {\n",
    "            if (arrLeft[leftIdx] < arrRight[rightIdx]) {\n",
    "                result[idx++] = arrLeft[leftIdx++]; // 将左侧较小的元素放入结果数组\n",
    "            } else {\n",
    "                result[idx++] = arrRight[rightIdx++]; // 将右侧较小的元素放入结果数组\n",
    "            }\n",
    "        }\n",
    "        \n",
    "        // 将左侧数组剩余的元素复制到结果数组\n",
    "        while (leftIdx < leftLen) {\n",
    "            result[idx++] = arrLeft[leftIdx++];\n",
    "        }\n",
    "        \n",
    "        // 将右侧数组剩余的元素复制到结果数组\n",
    "        while (rightIdx < rightLen) {\n",
    "            result[idx++] = arrRight[rightIdx++];\n",
    "        }\n",
    "        \n",
    "        return result;\n",
    "    }\n",
    "}\n",
    "\n",
    "int[] arr = {64, 34, 25, 12, 22, 11, 90};\n",
    "System.out.println(\"原始数组:\");\n",
    "printArray(arr); // 打印原始数组\n",
    "// 对数组进行归并排序\n",
    "int[] sortedArr = MergeSort.mergeSort(arr);\n",
    "System.out.println(\"\\n排序后的数组:\");\n",
    "printArray(sortedArr); // 打印排序后的数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **归并排序主函数** (`public static int[] mergeSort(int[] arr)`):\n",
    "   - **获取数组长度** (`int len = arr.length;`): 获取待排序数组的长度。\n",
    "   - **基础情况** (`if (len < 2) { return arr; }`): 如果数组长度小于2，则直接返回该数组，因为长度为1的数组本身就是有序的。\n",
    "   - **计算中间索引** (`int midIdx = len / 2;`): 计算数组的中间索引。\n",
    "   - **递归排序左右两边**:\n",
    "     - `int[] leftSorted = mergeSort(Arrays.copyOfRange(arr, 0, midIdx));`: 递归地对左半部分进行归并排序。\n",
    "     - `int[] rightSorted = mergeSort(Arrays.copyOfRange(arr, midIdx, len));`: 递归地对右半部分进行归并排序。\n",
    "   - **合并排序后的左右两边** (`return merge(leftSorted, rightSorted);`): 使用 `merge` 方法将两个已排序的数组合并为一个有序数组。\n",
    "\n",
    "2. **合并函数** (`private static int[] merge(int[] arrLeft, int[] arrRight)`):\n",
    "   - **初始化索引** (`int leftIdx = 0;`, `int rightIdx = 0;`, `int idx = 0;`): 初始化左右两个数组的索引以及结果数组的索引。\n",
    "   - **初始化结果数组** (`int[] result = new int[leftLen + rightLen];`): 创建一个新数组用于存放合并后的有序数组。\n",
    "   - **合并两个数组** (`while (leftIdx < leftLen && rightIdx < rightLen)`): 比较左右两个数组当前索引处的元素，将较小的元素放入结果数组。\n",
    "   - **处理剩余元素** (`while (leftIdx < leftLen)` 和 `while (rightIdx < rightLen)`): 将左右两个数组中未处理完的剩余元素依次放入结果数组。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 6、快速排序（Quick Sort）\n",
    "**算法步驟**\n",
    "\n",
    "1. 从序列中随机挑出一个元素，做为基准（pivot，这里选择序列的最左边元素作为基准）；\n",
    "1. 重新排列序列，将所有比基准值小的元素摆放在基准前面，所有比基准值大的摆在基准的后面。该操作结束之后，该基准就处于数列的中间位置。这个操作称为分区（partition）；\n",
    "1. 递归地把小于基准值元素的子序列和大于基准值元素的子序列进行上述操作即可。\n",
    "\n",
    "快速排序是一种高效的排序算法，通过选择一个基准值并将数组分为两部分，左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值，然后递归地对这两部分进行同样的操作，直到整个数组有序。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原始数组:\n",
      "64 34 25 12 22 11 90 \n",
      "排序后的数组:\n",
      "11 12 22 25 34 64 90 "
     ]
    }
   ],
   "source": [
    "public class QuickSort {\n",
    "\n",
    "    /**\n",
    "     * 快速排序算法实现。\n",
    "     * \n",
    "     * @param arr 待排序的整型数组\n",
    "     */\n",
    "    public static void quickSort(int[] arr) {\n",
    "        // 调用递归排序方法，传入数组和起始与结束索引\n",
    "        sort(arr, 0, arr.length - 1);\n",
    "    }\n",
    "\n",
    "    /**\n",
    "     * 递归排序方法。\n",
    "     * \n",
    "     * @param arr 待排序的整型数组\n",
    "     * @param left 起始索引\n",
    "     * @param right 结束索引\n",
    "     */\n",
    "    private static void sort(int[] arr, int left, int right) {\n",
    "        if (left < right) {\n",
    "            // 找到分区点，并以此点将数组分为两部分\n",
    "            int pivotIdx = partition(arr, left, right);\n",
    "            \n",
    "            // 递归排序左半部分\n",
    "            sort(arr, left, pivotIdx - 1);\n",
    "            \n",
    "            // 递归排序右半部分\n",
    "            sort(arr, pivotIdx + 1, right);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    /**\n",
    "     * 分区方法，用于确定分区点并将数组元素按大小分成两部分。\n",
    "     * \n",
    "     * @param arr 待分区的整型数组\n",
    "     * @param left 起始索引\n",
    "     * @param right 结束索引\n",
    "     * @return 分区点的索引\n",
    "     */\n",
    "    private static int partition(int[] arr, int left, int right) {\n",
    "        // 选取第一个元素作为基准值\n",
    "        int idx = left + 1; // 初始化索引\n",
    "        \n",
    "        // 从第二个元素开始遍历到结束索引\n",
    "        for (int i = idx; i <= right; i++) {\n",
    "            // 如果当前元素小于基准值，则将其交换到基准值之后\n",
    "            if (arr[left] > arr[i]) {\n",
    "                swap(arr, i, idx++); // 交换元素并更新索引\n",
    "            }\n",
    "        }\n",
    "        \n",
    "        // 将基准值交换到正确的位置\n",
    "        swap(arr, left, idx - 1);\n",
    "        \n",
    "        // 返回基准值的索引\n",
    "        return idx - 1;\n",
    "    }\n",
    "\n",
    "    /**\n",
    "     * 交换数组中两个元素的位置。\n",
    "     * \n",
    "     * @param arr 数组\n",
    "     * @param idx1 第一个元素的索引\n",
    "     * @param idx2 第二个元素的索引\n",
    "     */\n",
    "    private static void swap(int[] arr, int idx1, int idx2) {\n",
    "        int tmp = arr[idx1];\n",
    "        arr[idx1] = arr[idx2];\n",
    "        arr[idx2] = tmp;\n",
    "    }\n",
    "}\n",
    "\n",
    "int[] arr = {64, 34, 25, 12, 22, 11, 90};  \n",
    "System.out.println(\"原始数组:\");\n",
    "printArray(arr); // 打印原始数组\n",
    "QuickSort.quickSort(arr); // 对数组进行快速排序\n",
    "System.out.println(\"\\n排序后的数组:\");\n",
    "printArray(arr); // 打印排序后的数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **快速排序主函数** (`public static void quickSort(int[] arr)`):\n",
    "   - 调用递归排序方法 `sort`，传入数组和起始与结束索引。\n",
    "\n",
    "2. **递归排序方法** (`private static void sort(int[] arr, int left, int right)`):\n",
    "   - **递归终止条件** (`if (left < right)`): 如果起始索引小于结束索引，则继续排序。\n",
    "   - **分区操作** (`int pivotIdx = partition(arr, left, right);`): 调用分区方法 `partition`，找到分区点并以此点将数组分为两部分。\n",
    "   - **递归排序左右两部分**:\n",
    "     - `sort(arr, left, pivotIdx - 1);`: 递归排序左半部分。\n",
    "     - `sort(arr, pivotIdx + 1, right);`: 递归排序右半部分。\n",
    "\n",
    "3. **分区方法** (`private static int partition(int[] arr, int left, int right)`):\n",
    "   - **初始化索引** (`int idx = left + 1;`): 初始化一个索引 `idx` 用于记录基准值之后的小于等于基准值的元素的位置。\n",
    "   - **遍历数组** (`for (int i = idx; i <= right; i++)`): 从第二个元素开始遍历到结束索引。\n",
    "   - **交换元素** (`if (arr[left] > arr[i]) { swap(arr, i, idx++); }`): 如果当前元素小于基准值，则将其交换到基准值之后，并更新索引 `idx`。\n",
    "   - **将基准值交换到正确的位置** (`swap(arr, left, idx - 1);`): 将基准值交换到 `idx - 1` 的位置。\n",
    "   - **返回基准值的索引** (`return idx - 1;`): 返回基准值的索引。\n",
    "\n",
    "4. **交换方法** (`private static void swap(int[] arr, int idx1, int idx2)`):\n",
    "   - **交换数组中的两个元素**:\n",
    "     ```java\n",
    "     int tmp = arr[idx1];\n",
    "     arr[idx1] = arr[idx2];\n",
    "     arr[idx2] = tmp;\n",
    "     ```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 7、堆排序（Heap Sort）\n",
    "**算法步驟**\n",
    "\n",
    "1. 将待排序列$(R_0, R_1, ……, R_n)$构建成最大堆（最小堆）；\n",
    "1. 将堆顶元素R[0]与最后一个元素R[n]进行交换，此时得到新的无序区$(R_0, R_1, ……, R_{(n-1)})$和新的有序区$(R_n)$,且满足R[0, 1, ……, (n-1)]<=R[n]（>=R[n]）；\n",
    "1. 由于调整后的新堆可能违反堆的性质，因此需要对当前无序区$(R_0, R_1, ……, R_{(n-1)}$进行调整；\n",
    "1. 重复步骤2~3直到有序区的元素个数为n。\n",
    "\n",
    "堆排序首先通过构建最大堆来组织数据，然后不断取出堆顶元素（最大值），并调整剩余元素以维持堆的性质，直到所有元素都被排序。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原始数组:\n",
      "64 34 25 12 22 11 90 "
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "排序后的数组:\n",
      "11 12 22 25 34 64 90 "
     ]
    }
   ],
   "source": [
    "public class HeapSort {\n",
    "\n",
    "    // 定义一个静态变量来保存堆的当前长度\n",
    "    private static int heapLen;\n",
    "\n",
    "    /**\n",
    "     * 堆排序算法实现。\n",
    "     *\n",
    "     * @param arr 待排序的整型数组\n",
    "     */\n",
    "    public static void heapSort(int[] arr) {\n",
    "        // 初始化堆的长度为数组的长度\n",
    "        heapLen = arr.length;\n",
    "\n",
    "        // 构建最大堆\n",
    "        // 从最后一个非叶子节点开始调整，向上构建最大堆\n",
    "        for (int i = heapLen - 1; i >= 0; i--) {\n",
    "            heapify(arr, i);\n",
    "        }\n",
    "\n",
    "        // 从堆顶取出最大元素，并调整剩余的堆\n",
    "        for (int i = heapLen - 1; i > 0; i--) {\n",
    "            // 交换堆顶元素（最大值）和最后一个元素\n",
    "            swap(arr, 0, i);\n",
    "\n",
    "            // 减少堆的长度\n",
    "            heapLen--;\n",
    "\n",
    "            // 调整新的堆顶元素，使其满足最大堆性质\n",
    "            heapify(arr, 0);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    /**\n",
    "     * 调整指定节点以满足最大堆的性质。\n",
    "     *\n",
    "     * @param arr 待调整的整型数组\n",
    "     * @param idx 需要调整的节点的索引\n",
    "     */\n",
    "    private static void heapify(int[] arr, int idx) {\n",
    "        // 计算左右子节点的索引\n",
    "        int left = idx * 2 + 1;\n",
    "        int right = idx * 2 + 2;\n",
    "        int largest = idx; // 假设当前节点是最大的\n",
    "\n",
    "        // 如果左子节点存在，并且左子节点的值大于当前节点，则更新最大值索引\n",
    "        if (left < heapLen && arr[left] > arr[largest]) {\n",
    "            largest = left;\n",
    "        }\n",
    "\n",
    "        // 如果右子节点存在，并且右子节点的值大于当前最大值，则更新最大值索引\n",
    "        if (right < heapLen && arr[right] > arr[largest]) {\n",
    "            largest = right;\n",
    "        }\n",
    "\n",
    "        // 如果最大值索引不是当前节点的索引，则交换它们，并递归地调整子树\n",
    "        if (largest != idx) {\n",
    "            swap(arr, largest, idx);\n",
    "            heapify(arr, largest);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    /**\n",
    "     * 交换数组中两个元素的位置。\n",
    "     *\n",
    "     * @param arr 数组\n",
    "     * @param idx1 第一个元素的索引\n",
    "     * @param idx2 第二个元素的索引\n",
    "     */\n",
    "    private static void swap(int[] arr, int idx1, int idx2) {\n",
    "        int tmp = arr[idx1];\n",
    "        arr[idx1] = arr[idx2];\n",
    "        arr[idx2] = tmp;\n",
    "    }\n",
    "}\n",
    "\n",
    "int[] arr = {64, 34, 25, 12, 22, 11, 90};\n",
    "System.out.println(\"原始数组:\");\n",
    "printArray(arr); // 打印原始数组\n",
    "HeapSort.heapSort(arr); // 对数组进行堆排序\n",
    "System.out.println(\"\\n排序后的数组:\");\n",
    "printArray(arr); // 打印排序后的数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **构建最大堆** (`for (int i = heapLen - 1; i >= 0; i--) { heapify(arr, i); }`):\n",
    "   - 从最后一个非叶子节点开始调整，向上构建最大堆。这是因为叶子节点本身已经是最大堆（因为它们没有子节点）。\n",
    "   - 调用 `heapify` 方法确保每个节点都能满足最大堆的性质，即每个父节点的值都大于或等于其子节点的值。\n",
    "\n",
    "2. **排序过程** (`for (int i = heapLen - 1; i > 0; i--) { ... }`):\n",
    "   - 将堆顶元素（最大值）与最后一个元素交换，然后减少堆的长度。\n",
    "   - 调用 `heapify` 方法调整新的堆顶元素，使其满足最大堆的性质。\n",
    "   - 重复此过程，直到堆中只剩下一个元素。\n",
    "\n",
    "3. **调整最大堆** (`private static void heapify(int[] arr, int idx)`):\n",
    "   - 计算当前节点的左右子节点索引。\n",
    "   - 如果左子节点存在并且其值大于当前节点，则更新最大值索引。\n",
    "   - 如果右子节点存在并且其值大于当前最大值，则更新最大值索引。\n",
    "   - 如果最大值索引不是当前节点的索引，则交换它们，并递归地调整子树。\n",
    "\n",
    "4. **交换方法** (`private static void swap(int[] arr, int idx1, int idx2)`):\n",
    "   - 交换数组中两个元素的位置。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 8、计数排序（Counting Sort）\n",
    "**算法步驟**\n",
    "\n",
    "1. 找出数组中的最大值maxVal和最小值minVal；\n",
    "1. 创建一个计数数组countArr，其长度是maxVal-minVal+1，元素默认值都为0；\n",
    "1. 遍历原数组arr中的元素arr[i]，以arr[i]-minVal作为countArr数组的索引，以arr[i]的值在arr中元素出现次数作为countArr[a[i]-min]的值；\n",
    "1. 遍历countArr数组，只要该数组的某一下标的值不为0则循环将下标值+minVal输出返回到原数组即可。\n",
    "\n",
    "计数排序是一种非比较排序算法，适用于一定范围内的整数排序，通过统计每个值出现的次数来重构有序数组。它的优点是在特定条件下具有线性时间复杂度 \\(O(n+k)\\)，其中 \\(n\\) 是数组长度，\\(k\\) 是数值范围。缺点是空间复杂度较高，并且只适用于整数排序。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原始数组:\n",
      "64 34 25 12 22 11 90 -10 0 5 \n",
      "排序后的数组:\n",
      "-10 0 5 11 12 22 25 34 64 90 "
     ]
    }
   ],
   "source": [
    "public class CountingSort {\n",
    "\n",
    "    /**\n",
    "     * 计数排序算法实现。\n",
    "     *\n",
    "     * @param arr 待排序的整型数组\n",
    "     */\n",
    "    public static void countingSort(int[] arr) {\n",
    "        int len = arr.length; // 获取数组长度\n",
    "        \n",
    "        // 如果数组长度小于2，则无需排序\n",
    "        if (len < 2) return;\n",
    "\n",
    "        // 寻找数组中的最大值和最小值\n",
    "        int minVal = arr[0], maxVal = arr[0];\n",
    "        for (int i = 1; i < len; i++) {\n",
    "            if (arr[i] < minVal) {\n",
    "                minVal = arr[i]; // 更新最小值\n",
    "            } else if (arr[i] > maxVal) {\n",
    "                maxVal = arr[i]; // 更新最大值\n",
    "            }\n",
    "        }\n",
    "\n",
    "        // 创建一个辅助数组，用于统计每个值出现的次数\n",
    "        int[] countArr = new int[maxVal - minVal + 1];\n",
    "\n",
    "        // 统计每个值出现的次数\n",
    "        for (int val : arr) {\n",
    "            countArr[val - minVal]++; // 减去最小值，使下标从0开始\n",
    "        }\n",
    "\n",
    "        // 根据计数数组重建原数组\n",
    "        for (int arrIdx = 0, countIdx = 0; countIdx < countArr.length; countIdx++) {\n",
    "            // 对于每个计数大于0的值，将其写回原数组\n",
    "            while (countArr[countIdx]-- > 0) {\n",
    "                arr[arrIdx++] = minVal + countIdx; // 加上最小值，恢复实际值\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "int[] arr = {64, 34, 25, 12, 22, 11, 90, -10, 0, 5};\n",
    "System.out.println(\"原始数组:\");\n",
    "printArray(arr); // 打印原始数组\n",
    "CountingSort.countingSort(arr); // 对数组进行计数排序\n",
    "System.out.println(\"\\n排序后的数组:\");\n",
    "printArray(arr); // 打印排序后的数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **确定数组长度** (`int len = arr.length;`):\n",
    "   - 获取待排序数组的长度。\n",
    "\n",
    "2. **检查数组长度** (`if (len < 2) return;`):\n",
    "   - 如果数组长度小于2，则无需排序，直接返回。\n",
    "\n",
    "3. **查找最大值和最小值** (`int minVal = arr[0], maxVal = arr[0];`):\n",
    "   - 初始化最大值和最小值为数组的第一个元素。\n",
    "   - 遍历数组，更新最大值和最小值。\n",
    "\n",
    "4. **创建计数数组** (`int[] countArr = new int[maxVal - minVal + 1];`):\n",
    "   - 创建一个辅助数组 `countArr`，用于统计每个值出现的次数。数组的长度为最大值与最小值之差加1。\n",
    "\n",
    "5. **统计每个值出现的次数** (`for (int val : arr) { ... }`):\n",
    "   - 遍历原数组，统计每个值出现的次数。由于计数数组的下标从0开始，因此需要将每个值减去最小值 `minVal`，以便正确地映射到计数数组的下标上。\n",
    "\n",
    "6. **根据计数数组重建原数组** (`for (int arrIdx = 0, countIdx = 0; countIdx < countArr.length; countIdx++) { ... }`):\n",
    "   - 重新遍历计数数组，对于每个计数大于0的值，将其写回原数组。每次写回时，加上最小值 `minVal`，以恢复实际的值。\n",
    "\n",
    "7. **辅助方法** (`printArray`):\n",
    "   - 用于打印数组中的元素，便于观察排序结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 9、桶排序（Bucket Sort）\n",
    "**算法步驟**\n",
    "\n",
    "1. 设置一个bucketSize（该数值的选择对性能至关重要，性能最好时每个桶都均匀放置所有数值，反之最差），表示每个桶最多能放置多少个数值；\n",
    "1. 遍历输入数据，并且把数据依次放到到对应的桶里去；\n",
    "1. 对每个非空的桶进行排序，可以使用其它排序方法（这里递归使用桶排序）；\n",
    "1. 从非空桶里把排好序的数据拼接起来即可。\n",
    "\n",
    "\n",
    "桶排序是一种分布式的排序算法，通过将数据分布到若干个“桶”中，再对每个桶进行单独排序，最后将各个桶的结果合并起来得到最终的排序结果。桶排序适用于数据分布较为均匀的情况，可以有效地利用并行处理能力来加速排序过程。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原始列表:\n",
      "64 34 25 12 22 11 90 -10 0 5 \n",
      "\n",
      "排序后的列表:\n",
      "-10 0 5 11 12 22 25 34 64 90 \n"
     ]
    }
   ],
   "source": [
    "import java.util.ArrayList;\n",
    "import java.util.List;\n",
    "\n",
    "public class BucketSort {\n",
    "\n",
    "    /**\n",
    "     * 桶排序算法实现。\n",
    "     *\n",
    "     * @param arr 待排序的整型列表\n",
    "     * @param bucketSize 每个桶的大小\n",
    "     * @return 排序后的列表\n",
    "     */\n",
    "    public static List<Integer> bucketSort(List<Integer> arr, int bucketSize) {\n",
    "        int len = arr.size(); // 获取列表长度\n",
    "        \n",
    "        // 如果列表长度小于2或桶大小为0，则直接返回原列表\n",
    "        if (len < 2 || bucketSize == 0) {\n",
    "            return arr;\n",
    "        }\n",
    "\n",
    "        // 寻找列表中的最大值和最小值\n",
    "        int minVal = arr.get(0), maxVal = arr.get(0);\n",
    "        for (int i = 1; i < len; i++) {\n",
    "            if (arr.get(i) < minVal) {\n",
    "                minVal = arr.get(i); // 更新最小值\n",
    "            } else if (arr.get(i) > maxVal) {\n",
    "                maxVal = arr.get(i); // 更新最大值\n",
    "            }\n",
    "        }\n",
    "\n",
    "        // 计算所需的桶的数量\n",
    "        int bucketNum = (maxVal - minVal) / bucketSize + 1;\n",
    "\n",
    "        // 创建桶数组\n",
    "        List<List<Integer>> bucket = new ArrayList<>(bucketNum);\n",
    "        for (int i = 0; i < bucketNum; i++) {\n",
    "            bucket.add(new ArrayList<>()); // 初始化每个桶为空列表\n",
    "        }\n",
    "\n",
    "        // 将列表中的元素放入相应的桶中\n",
    "        for (int val : arr) {\n",
    "            int idx = (val - minVal) / bucketSize; // 计算元素所属的桶的索引\n",
    "            bucket.get(idx).add(val); // 将元素放入对应的桶中\n",
    "        }\n",
    "\n",
    "        // 对每个桶进行排序\n",
    "        for (int i = 0; i < bucketNum; i++) {\n",
    "            // 如果桶中有多个元素，则递归调用桶排序算法\n",
    "            if (bucket.get(i).size() > 1) {\n",
    "                bucket.set(i, bucketSort(bucket.get(i), bucketSize / 2)); // 递归调用桶排序\n",
    "            }\n",
    "        }\n",
    "\n",
    "        // 合并所有桶中的元素\n",
    "        List<Integer> result = new ArrayList<>();\n",
    "        for (List<Integer> val : bucket) {\n",
    "            result.addAll(val); // 将所有桶中的元素合并到结果列表中\n",
    "        }\n",
    "\n",
    "        return result;\n",
    "    }\n",
    "}\n",
    "\n",
    "// 辅助方法，用于打印列表中的元素\n",
    "public void printList(List<Integer> list) {\n",
    "    for (int num : list) {\n",
    "        System.out.print(num + \" \");\n",
    "    }\n",
    "    System.out.println();\n",
    "}\n",
    "\n",
    "//测试排序算法\n",
    "List<Integer> arr = new ArrayList<>();\n",
    "arr.add(64);\n",
    "arr.add(34);\n",
    "arr.add(25);\n",
    "arr.add(12);\n",
    "arr.add(22);\n",
    "arr.add(11);\n",
    "arr.add(90);\n",
    "arr.add(-10);\n",
    "arr.add(0);\n",
    "arr.add(5);\n",
    "System.out.println(\"原始列表:\");\n",
    "printList(arr); // 打印原始列表\n",
    "List<Integer> sortedArr = BucketSort.bucketSort(arr, 5); // 对列表进行桶排序\n",
    "System.out.println(\"\\n排序后的列表:\");\n",
    "printList(sortedArr); // 打印排序后的列表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **初始化参数** (`int len = arr.size();`):\n",
    "   - 获取待排序列表的长度。\n",
    "\n",
    "2. **检查列表长度和桶大小** (`if (len < 2 || bucketSize == 0) { return arr; }`):\n",
    "   - 如果列表长度小于2或桶大小为0，则无需排序，直接返回原列表。\n",
    "\n",
    "3. **查找最大值和最小值** (`int minVal = arr.get(0), maxVal = arr.get(0);`):\n",
    "   - 初始化最大值和最小值为列表的第一个元素。\n",
    "   - 遍历列表，更新最大值和最小值。\n",
    "\n",
    "4. **计算桶的数量** (`int bucketNum = (maxVal - minVal) / bucketSize + 1;`):\n",
    "   - 计算所需的桶的数量。每个桶的大小为 `bucketSize`，桶的数量为 `(最大值 - 最小值) / 桶大小 + 1`。\n",
    "\n",
    "5. **创建桶数组** (`List<List<Integer>> bucket = new ArrayList<>(bucketNum);`):\n",
    "   - 创建一个桶数组，每个桶是一个列表，用于存放相同范围内的元素。\n",
    "\n",
    "6. **分配元素到桶中** (`for (int val : arr) { ... }`):\n",
    "   - 遍历原列表，计算每个元素应放入哪个桶，并将其加入相应的桶中。\n",
    "\n",
    "7. **对每个桶进行排序** (`for (int i = 0; i < bucketNum; i++) { ... }`):\n",
    "   - 对每个桶进行排序。如果桶中有多个元素，则递归调用桶排序算法，桶大小减半。\n",
    "\n",
    "8. **合并桶中的元素** (`List<Integer> result = new ArrayList<>();`):\n",
    "   - 创建一个新的列表，用于存放排序后的结果。\n",
    "   - 遍历所有桶，将桶中的元素合并到结果列表中。\n",
    "\n",
    "9. **辅助方法** (`printList`):\n",
    "   - 用于打印列表中的元素，便于观察排序结果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 10、基数排序（Radix Sort）\n",
    "**算法步骤**\n",
    "\n",
    "1. 取得数组中的最大数，并取得位数，即为迭代次数n（例如：数组中最大数为123，则 n=3）；\n",
    "1. arr为原始数组，从最低位（或最高位）开始根据每位的数字组成radix数组（radix数组是个二维数组，其中一维长度为10），例如123在第一轮时存放在下标为3的radix数组中；\n",
    "1. 将radix数组中的数据从0下标开始依次赋值给原数组；\n",
    "1. 重复2~3步骤n次即可。\n",
    "\n",
    "基数排序是一种非比较排序算法，它通过按照每一位上的值将元素分配到不同的桶中，然后按照桶中的顺序重新构造数组来完成排序。基数排序适用于整数排序，尤其适用于位数较多的大整数排序。基数排序的时间复杂度为 \\(O(d(n+b))\\)，其中 \\(d\\) 是数字的最大位数，\\(n\\) 是数组长度，\\(b\\) 是基数（通常为 10）。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "原始数组:\n",
      "64 34 25 12 22 11 90 -10 0 5 \n",
      "排序后的数组:\n",
      "-10 0 5 11 12 22 25 34 64 90 "
     ]
    }
   ],
   "source": [
    "import java.util.ArrayList;\n",
    "import java.util.List;\n",
    "\n",
    "public class RadixSort {\n",
    "\n",
    "    /**\n",
    "     * 基数排序算法实现。\n",
    "     *\n",
    "     * @param arr 待排序的整型数组\n",
    "     */\n",
    "    public static void radixSort(int[] arr) {\n",
    "        // 如果数组长度小于2，则无需排序\n",
    "        if (arr.length < 2) return;\n",
    "\n",
    "        // 寻找数组中的最大值和最小值\n",
    "        int maxVal = arr[0];\n",
    "        int minVal = arr[0];\n",
    "        for (int a : arr) {\n",
    "            if (maxVal < a) {\n",
    "                maxVal = a; // 更新最大值\n",
    "            }\n",
    "            if (minVal > a) {\n",
    "                minVal = a; // 更新最小值\n",
    "            }\n",
    "        }\n",
    "\n",
    "        // 处理负数的情况\n",
    "        int offset = -minVal; // 负数转化为非负数的偏移量\n",
    "        int adjustedMax = maxVal + offset;\n",
    "\n",
    "        // 计算最大值的位数\n",
    "        int n = 1;\n",
    "        while (adjustedMax / 10 != 0) {\n",
    "            adjustedMax /= 10;\n",
    "            n++;\n",
    "        }\n",
    "\n",
    "        // 按照每一位进行排序\n",
    "        for (int i = 0; i < n; i++) {\n",
    "            // 创建10个桶，用于存放每一位上的数字\n",
    "            List<List<Integer>> radix = new ArrayList<>();\n",
    "            for (int j = 0; j < 10; j++) {\n",
    "                radix.add(new ArrayList<>()); // 初始化每个桶为空列表\n",
    "            }\n",
    "\n",
    "            // 将数组中的每个元素按照当前位数的值放入对应的桶中\n",
    "            int index;\n",
    "            for (int a : arr) {\n",
    "                // 提取当前位数上的值，调整回原始值范围\n",
    "                index = ((a + offset) / (int) Math.pow(10, i)) % 10;\n",
    "                radix.get(index).add(a); // 将元素放入对应的桶中\n",
    "            }\n",
    "\n",
    "            // 按照桶中的顺序重新构造数组\n",
    "            int pos = 0; // 用于跟踪数组中的位置\n",
    "            for (List<Integer> list : radix) {\n",
    "                for (int a : list) {\n",
    "                    arr[pos++] = a; // 将桶中的元素按顺序放回原数组\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "int[] arr = {64, 34, 25, 12, 22, 11, 90, -10, 0, 5};\n",
    "System.out.println(\"原始数组:\");\n",
    "printArray(arr); // 打印原始数组\n",
    "RadixSort.radixSort(arr); // 对数组进行基数排序\n",
    "System.out.println(\"\\n排序后的数组:\");\n",
    "printArray(arr); // 打印排序后的数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. **检查数组长度** (`if (arr.length < 2) return;`):\n",
    "   - 如果数组长度小于2，则无需排序，直接返回。\n",
    "\n",
    "2. **寻找最大值和最小值** (`int maxVal = arr[0]; int minVal = arr[0];`):\n",
    "   - 初始化最大值和最小值为数组的第一个元素。\n",
    "   - 遍历数组，更新最大值和最小值。\n",
    "\n",
    "3. **处理负数的情况** (`int offset = -minVal;`):\n",
    "   - 为了处理负数，需要将所有的数转换成非负数。`offset` 用于表示负数转化为非负数的偏移量。\n",
    "   - `adjustedMax` 用于存储调整后的最大值。\n",
    "\n",
    "4. **计算调整后最大值的位数** (`int n = 1; while (adjustedMax / 10 != 0) { ... }`):\n",
    "   - 初始化位数 `n` 为 1。\n",
    "   - 通过除以 10 并判断商是否为 0 来计算调整后最大值的位数。\n",
    "\n",
    "5. **按照每一位进行排序** (`for (int i = 0; i < n; i++) { ... }`):\n",
    "   - 对于调整后最大值的每一位，执行以下步骤：\n",
    "\n",
    "6. **创建桶数组** (`List<List<Integer>> radix = new ArrayList<>();`):\n",
    "   - 创建一个包含 10 个桶的数组，每个桶是一个列表，用于存放相同位数上的数字。\n",
    "\n",
    "7. **分配元素到桶中** (`for (int a : arr) { ... }`):\n",
    "   - 遍历数组中的每个元素，提取当前位数上的值，并将元素放入对应的桶中。\n",
    "   - 由于存在负数，所以需要先将元素加上偏移量 `offset`，然后再提取当前位数上的值。计算当前位数的方法是 `index = ((a + offset) / (int) Math.pow(10, i)) % 10`，其中 `i` 表示当前位数。\n",
    "\n",
    "8. **重新构造数组** (`int pos = 0; for (List<Integer> list : radix) { ... }`):\n",
    "   - 从桶中按顺序取出元素，并重新构造数组。\n",
    "   - 使用 `pos` 变量来跟踪数组中的当前位置，确保元素按顺序放回原数组。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "java",
   "pygments_lexer": "java",
   "version": "17.0.11+7-LTS-207"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
